The available bandwidth of a network path is the unused traffic capacity from end-to-end over the path. The capability of measuring the end-to-end available bandwidth of a communication network is useful in several contexts including admission control, service level agreement verification, intelligent routing, server selection, and network monitoring. The end-to-end available bandwidth can be determined by applying active measurement tools to identify the “weakest link in the chain”, the bottleneck link.
Several available-bandwidth measurement tools have been developed throughout the years. The majority of these are based on the probe rate model (PRM), which relies on self-induced congestion, i.e., injection of probe traffic at rates high enough to transiently overload the bottleneck link of the network path. The available bandwidth is strongly correlated to the probing-rate dependence of changes of the inter-packet time separation between consecutive packets. This time separation is expected to increase in case of congestion, which is observable at the probe receiver. This makes it feasible to estimate the available bandwidth, provided one has a reasonable model of the dependence of the time-separation increase on the probing rate and the available bandwidth.
If probe packets are sent at rates lower than the available bandwidth, the arrival rate of the probe packets at the receiver is expected to match the used transmission rate. If the probe-packet rate is higher than the minimum unused capacity, congestion occurs in the bottleneck router and the probe packets will be delayed; this increases the inter-packet time separation, which is observable at the probe receiver. By transmitting probe packets at various rates, it is feasible to measure the available bandwidth by identifying the point of congestion, i.e., the probe rate where the time separation starts to increase.
Other available-bandwidth measurement tools are based on a probe gap model (PGM). The PGM estimates the amount of cross traffic at the bottleneck router by exploiting the information in time-gap variations between two consecutive probe packets. The available bandwidth is estimated by subtracting the measured cross traffic from the bottleneck-link capacity.
In practice, PRM-based tools are more reliable than PGM tools, since the latter require knowledge of the bottleneck-link capacity in order to deliver reliable estimates. In addition, PGM tools also assume that the bottleneck link (i.e., the link with the minimum unused capacity) is the same as the narrow link (i.e., the link with the minimum capacity), which is not necessarily the case in reality.
In co-pending U.S. Patent Application Publication No. 2007/0115849, a bandwidth estimation method of this type, referred to as BART, is disclosed. The BART method applies Kalman filtering to bandwidth estimation. Kalman filtering is a numerical method allowing (under certain conditions) real-time estimation (“tracking”) of a system state which is not directly observable, but which can be indirectly measured by means of an observable quantity dependent on the system state. Kalman filtering has been successfully applied in many other engineering fields, but the BART method was the first time it was applied to the problem of estimating the available bandwidth of a network path.
FIG. 1 is a graphical representation of a model of inter-packet time separation change, or strain (ε), as a function of the probing rate, or probe traffic intensity (u). The strain ε is essentially zero, following line l1, until the probe traffic intensity reaches a level at which there is a break point 10. The break point is indicative of the available bandwidth (B). In an overload range above the break point, the strain ε increases linearly with increasing probe traffic intensity, following line l2. This linear relationship allows for Kalman filtering.
In the BART method, a sequence of probe-packet pairs, typically organized as a probe train, is transmitted for each measurement of the available bandwidth. The probe-packet rates are randomly chosen but constant for all packets within a probe sequence. Thus, the train of probe packets is transmitted equidistant in time, i.e., a number of probe pairs are sent at the same probing rate. The average inter-packet separation strain ε of all packet pairs in a measurement is used as the input to the Kalman filter; the output of the filter is the estimate of the sloping straight line l2.
Another known approach, referred to as pathChirp, injects probe packets that are not equidistant in time. Rather, the inter-packet time separation varies at the sender. This enables sampling at a wide range of probing rates at each sampling. PathChirp, however, employs a less efficient analysis method which does not take advantage of filtering methods such as Kalman filtering.